/*
 * 链表 (LinkedList) - C#实现
 * C#提供内置LinkedList<T>，这里演示自定义实现
 */

using System;

namespace DataStructures
{
    public class Node<T>
    {
        public T Data { get; set; }
        public Node<T> Next { get; set; }

        public Node(T data)
        {
            Data = data;
            Next = null;
        }
    }

    public class LinkedList<T>
    {
        private Node<T> _head;
        public int Count { get; private set; }

        public void Add(T data)
        {
            var newNode = new Node<T>(data);
            if (_head == null)
            {
                _head = newNode;
            }
            else
            {
                var current = _head;
                while (current.Next != null)
                    current = current.Next;
                current.Next = newNode;
            }
            Count++;
        }

        public void AddFirst(T data)
        {
            var newNode = new Node<T>(data) { Next = _head };
            _head = newNode;
            Count++;
        }

        public bool Remove(T data)
        {
            if (_head == null) return false;

            if (_head.Data.Equals(data))
            {
                _head = _head.Next;
                Count--;
                return true;
            }

            var current = _head;
            while (current.Next != null)
            {
                if (current.Next.Data.Equals(data))
                {
                    current.Next = current.Next.Next;
                    Count--;
                    return true;
                }
                current = current.Next;
            }
            return false;
        }

        public override string ToString()
        {
            var result = new System.Text.StringBuilder();
            var current = _head;
            while (current != null)
            {
                result.Append(current.Data);
                if (current.Next != null) result.Append(" → ");
                current = current.Next;
            }
            return result.ToString();
        }
    }

    public class LinkedListProgram
    {
        public static void Main()
        {
            Console.WriteLine("╔════════════════════════════════════════╗");
            Console.WriteLine("║   链表 (LinkedList) - C#实现           ║");
            Console.WriteLine("╚════════════════════════════════════════╝");

            var list = new LinkedList<int>();
            list.Add(10);
            list.Add(20);
            list.Add(30);
            list.AddFirst(5);
            Console.WriteLine($"\n链表: {list}");
            Console.WriteLine($"大小: {list.Count}");

            list.Remove(20);
            Console.WriteLine($"删除20后: {list}");

            Console.WriteLine("\n✅ 优势: 动态大小，插入删除O(1)");
            Console.WriteLine("⚠️ 局限: 访问O(n)，额外空间");
            Console.WriteLine("💡 应用: LRU缓存、撤销功能");
        }
    }
}
